import java.util.*;

public class ValidParentheses {
    public static boolean isValid(String s) {

        if(s.length() == 0) return true;
        if(s.length() % 2 == 1) return false;

        Stack<Character> stack = new Stack<Character>();
        stack.push(s.charAt(0));
        for(int i=1;i<s.length();i++){

            if(stack.size() == 0) {
                stack.push(s.charAt(i));
                continue;
            }
            
            char c = stack.peek();
            if((c == '(' && s.charAt(i) == ')')
               ||(c == '[' && s.charAt(i) == ']')
               ||(c == '{' && s.charAt(i) == '}')
               )
                stack.pop();
            else
                stack.push(s.charAt(i));
        }

        if(stack.size() == 0) return true;

        return false;
    }
    public static void main(String[] args) {
        String[] s = new String[4];
        s[0]="()";
        s[1]="()[]{}";
        s[2]="(]";
        s[3]="([])";

        for(int i=0;i<s.length;i++)
            System.out.println(isValid(s[i]));
    }
}